Основные определения и операции над языками

$\Sigma$ — конечное множество (**алфавит**) $\Sigma^*$ — множество всех конечных последовательностей элементов $\Sigma$ (**слов**, **строк**) $|w|$ — **длина** слова $w$, $\lambda$ — **пустое слово** (длины $0$) На $\Sigma^*$ задана операция **конкатенации** (умножения) слов Конкатенация **ассоциативна**, т.е. $\Sigma^*$ — **моноид** относительно конкатенации: * с **единицей** $\lambda$ * $\Sigma^*$ называют **свободным моноидом** или **моноидом слов** $L \subseteq \Sigma^*$ — **язык** (конечный или бесконечный)

* объединение $L_1 \cup L_2$ * пересечение $L_1 \cap L_2$ * дополнение $\overline{L} = \{w \in \Sigma^* \mid w \notin L\}$ * разность $L_1 \setminus L_2 = L_1 \cap \overline{L}_2$

$$L_1 L_2 = \{uv \mid u \in L_1, v \in L_2\}$$ Пример: $\{ab, abc\}\{ba, cba\} = \{abba, abcba, abccba\}$ Конкатенация ассоциативна $\implies$ умножение языков **ассоциативно** (и некоммутативно, разумеется). Естественно определяются степени языка: $L^n = L^{n-1}L,~~ L^0 = \{\lambda\}$

$$L^* = \bigcup\limits_{n=0}^{\infty} L^n$$ $\Sigma^*$ — это действительно результат применения итерации к языку $\Sigma$